/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 晓星航
 * Date: 2023-12-22
 * Time: 18:34
 */
import java.util.LinkedList;
import java.util.Queue;

public class MazeBFS {
    // 定义迷宫大小
    private static final int M = 8;
    private static final int N = 8;
    // 定义迷宫地图，0表示可以通过，1表示障碍物
    private static final int[][] MAP = {
            {0, 0, 0, 0, 0, 0, 0, 0},
            {0, 1, 1, 1, 0, 1, 1, 0},
            {0, 0, 0, 0, 0, 1, 1, 0},
            {0, 1, 0, 1, 1, 1, 0, 1},
            {0, 1, 0, 0, 0, 0, 0, 0},
            {0, 1, 1, 1, 1, 0, 1, 0},
            {0, 0, 0, 0, 1, 0, 0, 0},
            {0, 1, 1, 1, 0, 0, 1, 0}
    };
    // 定义起点和终点坐标
    private static final int START_X = 1;
    private static final int START_Y = 1;
    private static final int END_X = 6;
    private static final int END_Y = 6;

    public static void bfs() {
        boolean[][] visited = new boolean[M][N]; // 记录位置是否已经访问过
        int[][] distance = new int[M][N]; // 记录位置到起点的最短距离
        int[][] prevX = new int[M][N]; // 记录位置的前一个坐标X
        int[][] prevY = new int[M][N]; // 记录位置的前一个坐标Y

        Queue<Integer> queue = new LinkedList<>();
        queue.add(START_X * N + START_Y);
        visited[START_X][START_Y] = true;

        while (!queue.isEmpty()) {
            int cur = queue.poll();
            int curX = cur / N;
            int curY = cur % N;

            if (curX == END_X && curY == END_Y) { // 到达终点，输出路径
                printPath(prevX, prevY);
                return;
            }

            // 向四个方向扩展
            int[] dx = {-1, 0, 1, 0};
            int[] dy = {0, 1, 0, -1};
            for (int i = 0; i < 4; i++) {
                int nextX = curX + dx[i];
                int nextY = curY + dy[i];

                if (nextX >= 0 && nextX < M && nextY >= 0 && nextY < N
                        && MAP[nextX][nextY] == 0 && !visited[nextX][nextY]) {
                    queue.add(nextX * N + nextY);
                    visited[nextX][nextY] = true;
                    distance[nextX][nextY] = distance[curX][curY] + 1;
                    prevX[nextX][nextY] = curX;
                    prevY[nextX][nextY] = curY;
                }
            }
        }

        System.out.println("无法到达终点");
    }

    private static void printPath(int[][] prevX, int[][] prevY) {
        int x = END_X;
        int y = END_Y;

        while (x != START_X || y != START_Y) {
            System.out.println("(" + x + ", " + y + ")");
            int tempX = prevX[x][y];
            int tempY = prevY[x][y];
            x = tempX;
            y = tempY;
        }

        System.out.println("(" + START_X + ", " + START_Y + ")");
    }

    public static void main(String[] args) {
        bfs(); // 使用广度优先搜索求解迷宫问题
    }
}